package leetcode.D100.T23;

import util.ListNode;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: DYZ
 * @Create: 2022-02-18 10:14:40
 */

class Solution {
    // 一刷
    /*public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> queue = new PriorityQueue<>(lists.length+1, (front, back) -> front.val- back.val);
        for (ListNode list : lists) {
            if (list != null) {
                queue.add(list);
            }
        }
        ListNode head = new ListNode(), p = head;
        while (!queue.isEmpty()) {
            ListNode top = queue.poll();
            p.next = top;
            p = p.next;
            top = top.next;
            if (top != null) {
                queue.add(top);
            }
        }
        return head.next;
    }*/

    // 二刷
    /*public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode list : lists) {
            if (list != null)
                queue.offer(list);
        }
        ListNode head = new ListNode(), p = head;
        while (!queue.isEmpty()) {
            ListNode top = queue.poll();
            p.next = top;
            p = p.next;
            if (top.next != null)
                queue.offer(top.next);
        }
        return head.next;
    }*/

    // 三刷
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> (a.val - b.val));
        ListNode tHead = new ListNode(), tail = tHead;
        for (ListNode head : lists) {
            if (head != null)
                queue.offer(head);
        }
        while (!queue.isEmpty()) {
            ListNode head = queue.poll();
            tail.next = head;
            tail = tail.next;
            if (head.next != null)
                queue.offer(head.next);
        }
        return tHead.next;
    }
}
